package com.cheng.dataStructure.sparseArray;

/**
 * @User Administrator
 * @Classname SparseArray
 * @Project Data structure and algorithm
 * @Description 二维数组与稀疏数组之间的相互转换
 * @Author wpcheng
 * @Create 2021-06-21-9:42
 * @Version 1.0
 */
/**
 *  二维数组转换稀疏数组思路：
 *  1.遍历原始二维数组，得到有效数据（非0数据）的个数sum
 *  2.根据sum创建对应的稀疏数组int[sum+1][3];
 *  3.将有效数据存入稀疏数组
 *  4.打印稀疏数组
 *
 *  二维数组转换稀疏数组思路：
 *  1.根据稀疏数组的第一行创建二维数组
 *  2.遍历稀疏数组，将有效数据放入二维数组即可
 *  3.打印二维数组
 */
public class SparseArray {
    public static void main(String[] args) {
        //定义一个原始的二维数组
        int[][] arr1 = new int[11][11];
        arr1[1][2] = 8;
        arr1[2][3] = 16;
        //打印原始二维数组
        System.out.println("原始二维数组为：");
        for (int[] row : arr1) {    //先循环打印出数组的每一行
            for (int data : row) {  //再打印每一行的数据
                System.out.print("\t"+data);//格式化输出数组
            }
           System.out.println();//每一行打印完后就换行
        }
        //1.遍历原始二维数组，得到有效数据（非0数据）的个数
        int sum = 0;
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (arr1[i][j]!=0){
                    sum++;
                }
            }
        }
        System.out.println("有效数据（非0数据）的个数："+sum);
        //2.创建对应的稀疏数组
        int[][] sparseArr = new int[sum+1][3];
        //给稀疏数组赋值
        //第一行
        sparseArr[0][0] = 11;//二维数组的行数
        sparseArr[0][1] = 11;//二维数组的列数
        sparseArr[0][2] = sum;//有效数据（非0数据）的个数
        //遍历二维数组，将有效数据存入稀疏数组
        int count = 0;//count计数器，用于记录是第几个有效数据
        for (int i = 0; i < arr1.length; i++) {
            for (int j = 0; j < arr1.length; j++) {
                if (arr1[i][j]!=0){
                    count++;
                    sparseArr[count][0] = i;
                    sparseArr[count][1] = j;
                    sparseArr[count][2] = arr1[i][j];
                }
            }
        }
        //3.打印稀疏数组
        System.out.println("二维数组转换得到的稀疏数组为");
        for (int i = 0; i < sparseArr.length; i++) {
            System.out.println(sparseArr[i][0] + "\t"
                    + sparseArr[i][1]+"\t"
                    + sparseArr[i][2]+"\t");
        }
        //将稀疏数组还原成二位数组
        //1.根据稀疏数组的第一行创建二维数组
        int[][] arr2 = new int[sparseArr[0][0]][sparseArr[0][1]];
        //2.遍历稀疏数组，将有效数据放入二维数组
        for (int i = 1; i < sparseArr.length; i++) {
            arr2[sparseArr[i][0]][sparseArr[i][1]] = sparseArr[i][2];
        }
        //3.打印还原的二维数组
        System.out.println("稀疏数组还原得到的二维数组为：");
        for (int[] row : arr2) {
            for (int data : row) {
                System.out.print("\t"+data);
            }
            System.out.println();
        }
    }
}
